10. Stack Practice
Stack Practice
Question:
Remember that wonderful Python list we talked about eariler? It turns out that stack functionality is already built into it!
The
Python documentation
shows how you can use built-in funtions to turn your Python list into a stack.
pop()
is a given function, and
append()
is equivalent to a push function.
Of course, this functionality makes stack manipulation in Python all too easy. Let's make our own
Stack
class to see how a stack really works under the hood.
Start Quiz:
"""Add a couple methods to our LinkedList class,
and use that to implement a Stack.
You have 4 functions below to fill in:
insert_first, delete_first, push, and pop.
Think about this while you're implementing:
why is it easier to add an "insert_first"
function than just use "append"?"""
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def insert_first(self, new_element):
"Insert new element as the head of the LinkedList"
pass
def delete_first(self):
"Delete the first (head) element in the LinkedList as return it"
pass
class Stack(object):
def __init__(self,top=None):
self.ll = LinkedList(top)
def push(self, new_element):
"Push (add) a new element onto the top of the stack"
pass
def pop(self):
"Pop (remove) the first element off the top of the stack and return it"
pass
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
# Start setting up a Stack
stack = Stack(e1)
# Test stack functionality
stack.push(e2)
stack.push(e3)
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value
Solution:
There's a solution below. We had two options here—either pop and push from the first element in our linked list, or pop and push from the last element. We already had a function,
append()
, that adds an element to the end.
Why didn't we just come up with a function for removing the last element and call it a day? Every operation on a linked list must start with the head.
append()
thus traverses the whole list, taking O(n). Any operation on the last element requires us to traverse everything, so even though we had to write a new method our code will run much faster if we push/pop from the first element in a linked list.
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def insert_first(self, new_element):
new_element.next = self.head
self.head = new_element
def delete_first(self):
if self.head:
deleted_element = self.head
temp = deleted_element.next
self.head = temp
return deleted_element
else:
return None
class Stack(object):
def __init__(self,top=None):
self.ll = LinkedList(top)
def push(self, new_element):
self.ll.insert_first(new_element)
def pop(self):
return self.ll.delete_first()
INSTRUCTOR NOTE:
Here's an alternative solution to delete_first() - https://gist.github.com/adarsh0806/02d8e1d54d510294e75dfbc0d9bd7059
Benefits of this method:
1) this version has fewer lines of code with no loss of functionality
2) this version clears out the next field of the deleted element (good practice, even though it's not in the specification)